package pfc

private case class Term(coef: Double, exp: Int) {
  require(coef != 0 && exp >= 0)
  override def equals(other: Any): Boolean = other match {
    case that: Term => (that canEqual this) && (coef == that.coef) && (exp == that.exp)
    case _ => false
  }
  def canEqual(other: Any): Boolean = other.isInstanceOf[Term] 
}

class Pol private (private val terms: List[Term]) {
  // construtor auxiliar
  // (n.b.: tanto o construtor primario como o auxiliar sao privados)
  private def this(coef: Double, exp: Int) =
    this(if (coef == 0.0) (List[Term]())
    	else (List(new Term(coef, exp))))
  
  // aritmetica de polinomios
  def + (that: Pol): Pol = new Pol(Pol.add(this.terms, that.terms))
  def - (that: Pol): Pol = this + (-that)
  def * (that: Pol): Pol =
    if (!that.terms.isEmpty && !this.terms.isEmpty)
    	this * (that.terms, List[Term]())
    else new Pol(List[Term]())
  def * (terms:List[Term], list:List[Term]): Pol = terms.isEmpty match {
    case true => new Pol(list)
    case false => {
    	val term::novaTerms = terms
    	val novaLista = Pol.add(list, this.*(term).terms)
    	this.*(novaTerms, novaLista)
    }
  }
  	
  //retorna Tuple2[quociente, resto]
  def / (that: Pol): Tuple2[Pol, Pol] = this./(that, List[Term]())
  private def / (that: Pol, terms: List[Term]): Tuple2[Pol, Pol] = {
    require(!that.terms.isEmpty)
    if (this.terms.isEmpty) new Tuple2(new Pol(terms), this)      
    else if (that.terms.head.exp > this.terms.head.exp) new Tuple2(new Pol(terms), this)
	else {
	  val coef = this.terms.head.coef/that.terms.head.coef
	  val exp = this.terms.head.exp-that.terms.head.exp
	  (this.-(that.*(new Term(coef, exp))))./(that, Pol.add(List(new Term(coef,exp)),terms))
	}
  }
  // operadores unarios
  def unary_+ : Pol = this
  def unary_- : Pol = {
	var novaLista = List[Term]()
	for(term <- this.terms) {
      novaLista = Pol.add(novaLista, List(new Term(-(term.coef), term.exp)))
    }
    new Pol(novaLista)    
  }

  // aritmetica mista (o operando 1 e' um polinomio, o operando 2 e' um numero)
  def + (d: Double): Pol = this + (new Pol(List(new Term(d,0))))
  def - (d: Double): Pol = this + (-d)
  def * (d: Double): Pol = 
    if (d == 0) new Pol(List[Term]())
    else this * (new Pol(List(new Term(d, 0))))
  def / (d: Double): Pol = {
    require(d!=0)
    this * (1/d)
  }

  // grau, potenciacao e derivacao
  def degree: Int = terms.head.exp
  def ^(n: Int): Pol = this^(n+1, new Pol(List(new Term(1, 0))))
  private def ^(n: Int, that: Pol): Pol = {
    require(n>=0)
    n match {
    	case 0 => Pol(1)
    	case 1 => that
    	case _ => this^(n-1, this * that)
    }
  }
  def deriv: Pol = deriv(this.terms, List[Term]())
  private def deriv(terms: List[Term], novaLista: List[Term]): Pol = terms.isEmpty match {
      case true => new Pol(novaLista)
      case false => {
        val term::aux = terms
        if (term.exp==0) deriv(aux, novaLista)
        else deriv(aux, Pol.add(novaLista, List(new Term(term.coef * term.exp, term.exp-1))))
      }
  }
  def ! : Pol = this.deriv

  // calcula o valor do polinomio alvo para um dado valor de x
  def apply(x: Double): Double = {
    var result = 0.0
    for(term <- terms) {
      result += term.coef * (Math.pow(x, term.exp))
    }
    result
  }

  // composicao do polinomio alvo com outro polinomio
  def apply(that: Pol): Pol = {
    var novaLista = List[Term]()
    for(term <- this.terms) {
      novaLista = Pol.add(novaLista, ((that.^(term.exp)).*(term.coef)).terms)
    }
    new Pol(novaLista)
  }
  // sobrescrita de metodos da classe Any
  override def equals(other: Any): Boolean = other match {
    case that: Pol => (that canEqual this) && (terms == that.terms)
    case _ => false
  }
  def canEqual(other: Any): Boolean = other.isInstanceOf[Pol]
  
  override def hashCode: Int = hashCode(this.terms)
  def hashCode(terms: List[Term]): Int = terms.isEmpty match {
    case true => 0
    case false => {
      val term::aux = terms
      term.exp + 31 * (term.coef.toInt + 31 * (hashCode(aux) + 31)) 
    }
  }
  
  override def toString = this.terms.isEmpty match {
    case true => "0"
    case false => {
      val term::aux = this.terms
      printFirst(term) + toString(aux)
    }
  }
  private def printFirst(term: Term): String = term.exp match {
    case 0 => 
    	  if(term.coef>0) term.coef.toString 
    	  else "- " + (-term.coef).toString
    case 1 => term.coef match {
    		  case 1  => "x"
    		  case -1 => "- x"
    		  case _  => if(term.coef>0) term.coef.toString + "x"
    		  			else "- " + (-term.coef).toString + "x" 
        }
    case _ => term.coef match {
    		  case 1  => "x^" + term.exp.toString
    		  case -1 => "- x^" + term.exp.toString
    		  case _  => if(term.coef>0) term.coef.toString + "x^" + term.exp.toString
    		  			else "- " + (-term.coef).toString + "x^" + term.exp.toString
        }
  }
  private def toString(terms: List[Term]): String = terms.isEmpty match {
    case true => ""
    case false => {
      val term::aux = terms
      term.exp match {
        case 0 => 
    	  if(term.coef>0) " + " + term.coef.toString + toString(aux) 
    	  else " - " + (-term.coef).toString + toString(aux)
        case 1 => term.coef match {
    		  case 1  => " + x" + toString(aux)
    		  case -1 => " - x" + toString(aux)
    		  case _  => if(term.coef>0) " + " + term.coef.toString + "x" +
    			  			toString(aux)
    		  			else " - " + (-term.coef).toString + "x" + 
    		  				toString(aux)
        }
        case _ => term.coef match {
    		  case 1  => " + x^" + term.exp.toString + toString(aux)
    		  case -1 => " - x^" + term.exp.toString + toString(aux)
    		  case _  => if(term.coef>0) " + " + term.coef.toString + "x^" +
    			  			term.exp.toString + toString(aux)
    		  			else " - " + (-term.coef).toString + "x^" + 
    		  				term.exp.toString + toString(aux)
        }
      }
    }
  }
  
  // metodo auxiliar que multiplica o polinomio alvo por um termo simples
  private def * (term: Term): Pol = {
    var novaLista = List[Term]()
    for(termo <- this.terms) {
      novaLista = Pol.add(novaLista, List(new Term(term.coef*termo.coef, term.exp+termo.exp)))
    }
    new Pol(novaLista)
  }
}

object Pol {

  // conversao implicita de Double em Pol
  implicit def doubleToPol(d: Double): Pol = Pol(d)

  // metodos de fabrica acessiveis para os clientes
  def apply(coef: Double, exp: Int): Pol = new Pol(coef, exp)
  def apply(coef: Double): Pol = new Pol(coef, 0)

  // metodo de fabrica interno (serve apenas para evitar o uso de new)
  private def apply(terms: List[Term]): Pol = new Pol(terms) 

  // metodo auxiliar para as operacoes de adicao e subtracao de polinomios
  private def add(terms1: List[Term], terms2: List[Term]): List[Term] =
    add(terms1, terms2, List[Term]())
  private def add(terms1: List[Term], terms2: List[Term], merged: List[Term]): List[Term] = {
    if (terms1.isEmpty && terms2.isEmpty) invert(merged, List[Term]()) 
    else if (terms1.isEmpty) {
      val term::aux = terms2
      add(terms1, aux, term::merged)
    }
    else if (terms2.isEmpty) {
      val term::aux = terms1
      add(terms2, aux, term::merged)
    }
    else {
      val term1::aux1 = terms1
      val term2::aux2 = terms2
      if (term1.exp > term2.exp) add(aux1, terms2, term1::merged)
      else if (term1.exp < term2.exp) add(terms1, aux2, term2::merged)
      else if (term1.coef == -term2.coef) add(aux1, aux2, merged)
      else add(aux1, aux2, new Term(term1.coef + term2.coef, term1.exp)::merged)
    }
  }
  private def invert(original: List[Term], invertida: List[Term]): List[Term] = {
    if (original.isEmpty) invertida
    else {
      val term::aux = original
      invert(aux, term::invertida)
    }
  }
}